package leetcode;

import java.util.*;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-15 01:12
 **/
public class LeetCode851 {

    public int[] loudAndRich(int[][] richer, int[] quiet) {
        int n = quiet.length;
        //充当图,维护所有的边
        List<Integer>[] g = new List[n];
        for (int i = 0; i < n; i++) {
            g[i] = new ArrayList<>();
        }

        //入度表
        int[] inDeg = new int[n];
        for (int[] arr : richer) {
            //添加边,arr[0]和arr[1]相当于两个顶点
            g[arr[0]].add(arr[1]);
            //点arr[1]的入度自增
            ++inDeg[arr[1]];
        }

        //结果
        int[] res = new int[n];
        //初始化数组,如果某个点入度为0,那么该点的res[i]=i
        for (int i = 0; i < n; i++) {
            res[i] = i;
        }

        //队列维护入度为0的点
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (inDeg[i] == 0) {
                queue.offer(i);
            }
        }

        //遍历所有的点,将对应的值赋到结果数组中
        while (!queue.isEmpty()) {
            int x = queue.poll();

            g[x].forEach(y -> {
                //更新所有比personx穷的persony的res[y],如果quiet[res[x]]比quiet[res[y]]小,则res[y] = res[x]
                if (quiet[res[x]] < quiet[res[y]]) {
                    res[y] = res[x];
                }

                //如果以x为起点的边的终点的集合对应的入度-1后为0,将其加入到队列中
                if (--inDeg[y] == 0) {
                    queue.offer(y);
                }
            });
        }

        //返回结果
        return res;
    }

}
